The present invention relates generally to computer graphics, and more particularly to rendering three-dimensional volume and point-sample data with splatting methods.
Laser range and image-based scanning can produce complex and visually stunning three-dimensional (3D) images. However, scanning produces a huge number of point-samples. Hereinafter, a point-sample is defined as a zero-dimensional point in space having (x,y,z) coordinates. Typically, the point-samples do not have connectivity information. That is, the point-samples are not related or linked. This makes it difficult to render point-samples as images.
One common way to connect the point-samples is with polygon (triangle) meshes, and then to render the meshes. However, some meshes are too large to be rendered interactively, and many applications cannot tolerate the inherent loss in geometric accuracy and texture fidelity that comes from polygon reduction. Recent efforts have focused on direct rendering of unconnected point-samples. These techniques use hierarchical data structures and forward warping to render the point-samples efficiently.
One important challenge for point rendering is to properly reconstruct an image of a continuous surface from irregularly spaced point-samples. The image must be correct, and independent of the order in which the point-samples are rendered. Very often, the point-samples must appear as a continuous opaque or translucent surface while maintaining the high texture fidelity of the scanned data. In addition, point rendering should correctly handle hidden surface removal and transparency.
In the prior art, texture mapping is frequently used to xe2x80x9cfill-inxe2x80x9d the surface areas between the point-samples. Texture mapping increases the visual complexity of models by mapping functions for color, normals, or other material properties onto the model surfaces. If these texture functions are inappropriately band-limited, texture aliasing may occur during the projection to raster images. In addition, texture mapping is mostly used for surface rendering. Volume rendering is important for visualizing acquired and simulated data sets in scientific and engineering applications. Volume rendering reconstructs a 3D function from discrete sample points, transforms the 3D function into screen space, and then evaluates opacity integrals along line-of-sights, called xe2x80x9crays.xe2x80x9d
In interactive volume rendering, splatting approximate this procedure, see Westover xe2x80x9cInteractive Volume Rendering,xe2x80x9d Upson, editor, Proceedings of the Chapel Hill Workshop on Volume Visualization, pages 9-16, University of North Carolina at Chapel Hill, Chapel Hill, N.C., May 1989. Westover does not deal with aliasing problems, which lead to noticeable artifacts such as jagged silhouette edges and Moirxc3xa9 patterns in textures.
With splatting, the volume data is interpreted as a field of 3D reconstruction kernels, one kernel for each particle, voxel, or discrete sample point. Each 3D reconstruction kernel absorbs and emits light. Integrals are predetermined separately across each 3D kernel, resulting in xe2x80x9cfootprintxe2x80x9d functions. Each footprint function xe2x80x9cspreadsxe2x80x9d the contribution of each point over nearby pixels in the image. Typically, the span of the footprint is in the order of two to five pixels. The xe2x80x9csmearedxe2x80x9d contributions of each discrete sample point of the 3D volume are composited, i.e., accumulated, in a front-to-back or back-to-front order to produce the pixels of the output image.
Prior art splatting suffers from inaccurate visibility determination when compositing the splats in the back-to-front order. This leads to visible artifacts such as color bleeding. This problem can be solved by using an axis-aligned sheet buffer, see Westover xe2x80x9cFootprint Evaluation for Volume Rendering,xe2x80x9d Computer Graphics, Proceedings of SIGGRAPH 90, pages 367-376, 1990. However, that solution produces disturbing xe2x80x9cpoppingxe2x80x9d artifacts in animations.
Popping is the term used to describe discontinuous intensity changes between subsequent images in the animation sequence. The sheet buffer can also be aligned parallel to the image plane, see Mueller et al. xe2x80x9cEliminating Popping Artifacts in Sheet Buffer-Based Splatting,xe2x80x9d IEEE Visualization ""98, pages 239-246, 1998. They also splat several slices of each 3D reconstruction kernel separately. Their technique is similar to slice-based volume rendering, and does not suffer from popping artifacts.
Splatting can be combined with ray casting techniques to accelerate rendering with perspective projection. Hierarchical splatting allows progressive refinement during rendering. Furthermore, splatting can also be applied on a volume data set represented as wavelets.
Aliasing artifacts may occur in areas of the volume where the sampling rate along diverging rays falls below the volume grid sampling rate. A distance-dependent function can xe2x80x9cstretchxe2x80x9d the footprints to make them act as low-pass filters, see Swan et al. xe2x80x9cAnti-Aliasing Technique for Splatting,xe2x80x9d Proceedings of the 1997 IEEE Visualization Conference, pages 197-204, 1997. Swan adjusts the size of the footprints according to the distance between the samples and the image plane. Swan is distinguished in greater detail below.
Additional care has to be taken when the 3D reconstruction kernels are not radially symmetric, as is the case for rectilinear, curvilinear, or irregular grids. In addition, for an arbitrary position in 3D space, contributions from all kernels must sum up to one. Otherwise, artifacts such as splotches occur in the image. For rectilinear grids, elliptical footprints can be warped to a circular footprint, see Westover xe2x80x9cInteractive Volume Rendering,xe2x80x9d Upson, editor, Proceedings of the Chapel Hill Workshop on Volume Visualization, pages 9-16. University of North Carolina at Chapel Hill, Chapel Hill, N.C., May 1989. To render curvilinear grids, a stochastic Poisson resampling can generate a set of new points whose footprints are spheres or ellipsoids, see Mao xe2x80x9cSplatting of Non Rectilinear Volumes Through Stochastic Resampling,xe2x80x9d IEEE Transactions on Visualization and Computer Graphics, 2(2):156-170, 1996.
Heckbert, in xe2x80x9cFundamentals in Texture Mapping and Image Warpingxe2x80x9d Master""s Thesis, University of California at Berkeley, Department of Electrical Engineering and Computer Science, 1989, describes a rendering method that uses elliptical weighted average (EWA) filters to avoid aliasing of surface textures. However, that method only operates on 2D regularly sampled texture. In other words, that method can not be used directly with irregular point samples or volume data sets.
Therefore, there is a need for a splatting method that can render a volume data set including irregularly spaced sample points without blurring, aliasing, popping, and other annoying artifacts present with prior art splatting techniques.
The present invention provides a novel rendering method that combines the projection of an elliptical 3D Gaussian reconstruction kernel function with a elliptical 2D Gaussian low-pass filter to produce a single splat primitive a screen space, that is an EWA continuous resampling filter. This 2D EWA resampling filter can be applied directly to discrete sample points in screen space. The EWA resampling filter according to the invention prevents aliasing artifacts and excessive blurring in the image. Moreover, the invention works with arbitrary elliptical 3D Gaussian reconstruction kernels and arbitrary Gaussian low-pass filter functions, and efficiently supports rectilinear, curvilinear, and irregular volumes, and perspective projection.
The method according to the invention is based on a novel framework to determine the continuous 2D EWA resampling filter. Effectively, the method transforms the volume data set, or any other set of discrete sample points defined in object space, first to camera space, then to ray space, and finally to screen space. This transformation is equivalent to a projection, e.g. a perspective or orthonormal projection. By using a local affine approximation at each discrete sample point, we combined the continuous 3D reconstruction kernel and 2D filter functions into a single analytic expression, i.e., the continuous 2D EWA resampling filter. We then apply the continuous EWA resampling filter each discrete sample point in screen space to reconstruct a continuous image. Then, the continuous image can be directly rasterized by a rendering engine using, for example, forward differencing with a single 1D footprint table for all resampling filters and any viewing direction. Other rendering techniques to convert the continuous functions to pixels of the output image can also be used.
The splat primitive according to the invention can be integrated easily into conventional splatting methods. Because of the flexibility of this splatting primitive, it can be utilized to render rectilinear, curvilinear, or irregular volume data sets. By xe2x80x9cflatteningxe2x80x9d the continuous resampling filter along the volume gradient, surface splats that are suitable for high quality iso-surface rendering can easily be computed.
More specifically, the invention provides a method for producing an image from a set of discrete sample points. The sample points can define a 3D volume or surface. Each discrete sample point is projected to a screen space. A continuous resampling filter for each sample point is generated in screen space. The continuous resampling filter is a combination of a continuous reconstruction function and a continuous filter function for the sample point in screen space. The continuous resampling filter is then applied to each corresponding discrete sample in the screen space to generate a continuous sample for the image. The continuous samples can be rasterized to pixels using any known rasterization process or method.